/*
符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
public:
    int peakIndexInMountainArray(vector<int> &arr)
    {
        return find(arr, 0, arr.size());
    }
    int find(vector<int> &arr, int l, int r)
    {
        int mid = (l + r) / 2;
        if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
        {
            return mid;
        }
        else if (arr[mid] < arr[mid + 1])
        {
            return find(arr, mid + 1, r);
        }
        else
        {
            return find(arr, l, mid - 1);
        }
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    vector<int> arr = {24,69,100,99,79,78,67,36,26,19};
    cout << s.peakIndexInMountainArray(arr) << endl;
    return 0;
}
